﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;

namespace TestProject
{
    public partial class DrawLine : Form
    {
        public DrawLine()
        {
            InitializeComponent();
        }
        /*
         *Reference From : http://www.myexception.cn/c-sharp/80214.html
         *Title          : [研究]不规则坐标（可看作二维数组）分组算法。欢迎所有有兴趣研究算法的人。该如何解决
         *By             : EndlessRain 
         *Date           : Sep 15,2013 08:34 Sunday
         */
        private void Form1_Paint(object sender, PaintEventArgs e)
        {
            int gridSize = 20;
            for (int i = 0; i * gridSize < ClientSize.Width; i++)
            {
                e.Graphics.DrawString(i.ToString("00"), Font, Brushes.Black,
                  i * gridSize - 5, 0);
                e.Graphics.DrawLine(Pens.Gray, i * gridSize, gridSize,
                  i * gridSize, ClientSize.Height);
            }
            for (int i = 0; i * gridSize < ClientSize.Height; i++)
            {
                e.Graphics.DrawString(i.ToString("00"), Font, Brushes.Black, 0,
                  i * gridSize - 5);
                e.Graphics.DrawLine(Pens.Gray, gridSize, i * gridSize,
                  ClientSize.Width, i * gridSize);
            }

            for (int i = 0; i < points.Length; i++)
                e.Graphics.DrawEllipse(Pens.Red,
                  (points[i].X + 1) * gridSize - 3, (points[i].Y + 1) * gridSize - 3,
                  6, 6);

            for (int i = 0; i < groups.Count; i++)
            {
                int minX = int.MaxValue, minY = int.MaxValue,
                  maxX = int.MinValue, maxY = int.MinValue;
                for (int j = 0; j < groups[i].Count; j++)
                {
                    Point p = groups[i][j];
                    minX = p.X < minX ? p.X : minX;
                    minY = p.Y < minY ? p.Y : minY;
                    maxX = p.X > maxX ? p.X : maxX;
                    maxY = p.Y > maxY ? p.Y : maxY;
                }
                Rectangle r = Rectangle.FromLTRB(
                  (minX + 1) * gridSize - 5, (minY + 1) * gridSize - 5,
                  (maxX + 1) * gridSize + 5, (maxY + 1) * gridSize + 5);
                e.Graphics.DrawRectangle(Pens.Blue, r);
                e.Graphics.DrawString(i.ToString(), Font, Brushes.Black, r);
            } 
        }
        private const int pointCount = 100;
        private Point[] points = new Point[pointCount];
        private bool[] scans; // 是否计算过 
        private List<List<Point>> groups = new List<List<Point>>();
        private void search(int index, List<Point> group)
        {
            if (scans[index]) return;
            scans[index] = true; // 标记已被扫描 
            Point point = points[index];
            group.Add(point);
            for (int i = 0; i < points.Length; i++)
            {
                if (scans[i]) continue;
                if ((point.X == points[i].X && Math.Abs(point.Y - points[i].Y) == 1) ||
                  (point.Y == points[i].Y && Math.Abs(point.X - points[i].X) == 1))
                {
                    search(i, group);
                }
            }
        }

        private void Calc()
        {
            scans = new bool[pointCount];
            groups.Clear();
            for (int i = 0; i < points.Length; i++)
            {
                if (scans[i]) continue; //计算过 
                List<Point> group = new List<Point>();
                groups.Add(group);
                search(i, group);
            }
            Console.WriteLine(groups.Count);
        }

        private void button1_Click(object sender, EventArgs e)
        {
            Random random = new Random();
            for (int i = 0; i < points.Length; i++)
            {
                points[i].X = random.Next(20);
                points[i].Y = random.Next(20);
            }
            Calc();
            Invalidate();
        }
    }
}
